home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / incl / LEDA / impl / f_heap.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  3.7 KB  |  168 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  f_heap.h
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. #ifndef LEDA_FHEAP_H
  18. #define LEDA_FHEAP_H
  19.  
  20. //------------------------------------------------------------------------------
  21. //
  22. // Fibonacci Heap
  23. //
  24. // Michael Muth  (1988)
  25. //
  26. // Modifications
  27. //
  28. // - virtual compare function  (Stefan Naeher, August 1989)
  29. //
  30. // - virtual clear functions   (Stefan Naeher, April 1990)
  31. //
  32. //------------------------------------------------------------------------------
  33.  
  34.  
  35. #include <LEDA/basic.h>
  36.  
  37.  
  38. class f_heap_node  {
  39. // repraesentiert Knoten und Heap geordnete Baeume
  40.  
  41. friend class f_heap;
  42.  
  43.    f_heap_node* next;          // used to link all used items 
  44.    f_heap_node* pred;          
  45.  
  46.    f_heap_node* left;          // left and right siblings (circular List)
  47.    f_heap_node* right;   
  48.    f_heap_node* parent;        // parent node
  49.    f_heap_node* children;      // a child
  50.  
  51.    int  rank;                   // number of children
  52.    char mark;                   // ( 1=true, 0=false )
  53.  
  54.    GenPtr key;                  // key
  55.    GenPtr inf;                  // information
  56.  
  57.  
  58. // size: 10 words =  40 bytes
  59.  
  60.  
  61.    void link(f_heap_node*);
  62.    void cut(f_heap_node*);
  63.  
  64.  
  65. public:
  66.  
  67.    f_heap_node(GenPtr k, GenPtr i, f_heap_node* n) 
  68.    {  key = k;
  69.       inf = i;
  70.       next = n;
  71.       pred = 0;
  72.       rank = 0;
  73.       mark = 0;
  74.       parent = 0;
  75.       children = 0;
  76.  
  77.       if (n) n->pred = this;
  78.  
  79.     }  // end of f_heap_node()
  80.  
  81.  
  82.   LEDA_MEMORY(f_heap_node)
  83.  
  84.  };  //f_heap_node
  85.  
  86.  
  87. typedef f_heap_node* f_heap_item;
  88.  
  89.  
  90. class f_heap
  91.  /* Ein F-Heap enthaelt eine zirkulaere Liste von Heap geordneten
  92.     Baeumen. Der Einstieg erfolgt ueber den minptr, einen Zeiger
  93.     auf den Baum mit kleinstem Schluessel in der Wurzel. Die ei-
  94.     gentlichen Items ( Paare aus NxT ) sind in den Knoten der
  95.     Baeume enthalten.                                               */
  96.  { 
  97.    int node_count;         // number of nodes
  98.    f_heap_node* minptr;    // entry to the List of roots
  99.    f_heap_node* node_list; // List of all nodes
  100.  
  101.    int max_rank() const;
  102.  
  103.    f_heap_node* new_f_heap_node(GenPtr k, GenPtr i)
  104.    { return  node_list = new f_heap_node(k,i,node_list); }
  105.  
  106.    virtual int cmp(GenPtr x, GenPtr y) const { return compare(x,y); }
  107.  
  108.    virtual void print_key(GenPtr)  const {}
  109.    virtual void print_inf(GenPtr)  const {}
  110.  
  111.    virtual void clear_key(GenPtr&)  const {}
  112.    virtual void clear_inf(GenPtr&)  const {}
  113.  
  114.    virtual void copy_key(GenPtr&)   const {}
  115.    virtual void copy_inf(GenPtr&)   const {}
  116.  
  117.    virtual int  int_type() const { return 0; }
  118.  
  119. protected:
  120.  
  121.   f_heap_node* item(void* p) const { return (f_heap_node*)p; }
  122.  
  123. public:
  124.  
  125.  f_heap();
  126.  f_heap(const f_heap&);
  127.  f_heap& operator=(const f_heap&);
  128.  
  129. virtual ~f_heap()  { clear(); }
  130.  
  131.  
  132. f_heap_node* insert(GenPtr, GenPtr);
  133. f_heap_node* find_min() const { return(minptr); }
  134.  
  135. void del_min();  
  136. void decrease_key(f_heap_node*,GenPtr);
  137. void change_inf(f_heap_node*,GenPtr);
  138. void del_item(f_heap_node *x){ decrease_key(x,minptr->key); del_min();}
  139. void clear();
  140.  
  141. GenPtr  key(f_heap_node *x) const { return x->key ; }
  142. GenPtr  inf(f_heap_node *x) const { return x->inf; }
  143.  
  144.   
  145. int  size()  const { return node_count; }
  146. int  empty() const { return (find_min()==0) ? true : false; }
  147.  
  148.  
  149. // Iteration:
  150.  
  151.  
  152. f_heap_node* first_item() const;
  153.  
  154. f_heap_node* next_item(f_heap_node* p) const;
  155.  
  156.  
  157.  
  158. };  // end of class f_heap
  159.  
  160.  
  161. // dummy I/O and cmp functions
  162.  
  163. inline void Print(const f_heap&, ostream&) { }
  164. inline void Read (f_heap&, istream&) { }
  165. inline int  compare(const f_heap&,const f_heap&) { return 0; }
  166.  
  167. #endif
  168.